/*
 * @lc app=leetcode id=43 lang=cpp
 *
 * [43] Multiply Strings
 */
class Solution {
public:
    string multiply(string num1, string num2) {
        int l1 = num1.size();
        int l2 = num2.size();

        string ret(l1+l2, '0');

        for (int i=l1-1; i>=0; i--) {
            for (int j=l2-1; j>=0; j--) {
                int sum = ret[i+j+1] - '0';
                sum += (num1[i]-'0') * (num2[j]-'0');

                ret[i+j+1] = sum%10 + '0';
                ret[i+j] += sum/10;
            }
        }

        int i = 0;
        while (i < l1+l2) {
            if (ret[i] != '0' || i == l1+l2-1) {
                return ret.substr(i, l1+l2-i);
            }
            i++;
        }
        return "0";
    }
    string multiply2(string num1, string num2) {
        int l1 = num1.size();
        int l2 = num2.size();
        if (l1 < 1 || l2 < 1) {
            return "0";
        }

        if (num1.compare("0") == 0 || num2.compare("0") == 0) {
            return "0";
        }

        string ret;

        for (int i=l1-1; i>=0; i--) {
            string tmp;
            int sum = 0;
            int val = num1[i]-'0';
            for (int j=l2-1; j>=0; j--) {
                sum += val * (num2[j]-'0');
                tmp += (char)(sum%10)+'0';
                sum /= 10;
            }

            if (sum > 0) {
                tmp += ((char)sum + '0');
            }
            reverse(tmp.begin(), tmp.end());
            ret = addition(ret, tmp, l1-1-i);
        }
        return ret;
    }

    string addition(string ret, string tmp, int n) {
        tmp = tmp+string(n, '0');
        int l1 = ret.size();
        int l2 = tmp.size();
        int i = l1-1, j = l2-1;

        int sum = 0;
        string result;
        while (i >= 0 || j >= 0) {
            if (i >= 0) {
                sum += ret[i]-'0';
                i--;
            }
            if (j >= 0) {
                sum += tmp[j]-'0';
                j--;
            }
            result += (char)(sum%10) + '0';
            sum /= 10;
        }

        if (sum > 0) {
            result += (char)sum + '0';
        }
        reverse(result.begin(), result.end());

        return result;
    }
};

